1367C - Social Distance - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef vector<int> vi;
typedef pair<int, int> pi;
#define sa cout << "YES" << endl
#define wa cout << "NO" << endl
int M = 1000000007;

// void dfs(int i, int j, vector<string> &v)
// {
//     if (i < 0 || j < 0)
//     {
//         return;
//     }
//     if (i >= v.size() || j >= v[0].length())
//     {
//         return;
//     }
//     if (v[i][j] == '.' || v[i][j] == '+')
//     {
//         return;
//     }

//     v[i][j] = '+';

//     dfs(i + 1, j, v);
//     dfs(i - 1, j, v);
//     dfs(i, j + 1, v);
//     dfs(i, j - 1, v);
// }
// bool cmp(pair<int, int> a, pair<int, int> b)
// {

//     return a.ss - a.ff < b.ss - b.ff;
// }
// int dp[1000002];
// vector<int> v;
// int func(int n)
// {
//     if (n == 0)
//         return 1;
//     if (dp[n] != -1)
//     {
//         return dp[n];
//     }
//     int ways = 0;

//     for (int i = 0; i < v.size(); i++)
//     {
//         if (n - v[i] >= 0)
//             ways += func(n - v[i]) % M;
//     }
//     return dp[n] = ways % M;
// }

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("div7.in", "r", stdin);
    // freopen("div7.out", "w", stdout);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int k;
        cin >> k;

        string s;
        cin >> s;
        int ans = 0;
        vector<int> pos;
        int count = 0;
        int ind = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '0')
            {
                count++;
                if (i == s.size() - 1)
                {
                    if (count >= 1)
                    {
                        ans += (count + k) / (k + 1);
                        ind = i + 1;
                    }
                }
            }
            else
            {
                if (count >= k + 1)
                {
                    ans += (count) / (k + 1);
                }
                ind = i + 1;
                break;
            }
        }
        count = 0;
        for (int i = ind; i < s.size(); i++)
        {
            if (s[i] == '0')
            {
                count++;
                if (i == s.size() - 1)
                {
                    if (count >= k + 1)
                    {
                        ans += (count) / (k + 1);
                    }
                }
            }
            else
            {
                if (count >= 2 * k + 1)
                {
                    ans += (count - k) / (k + 1);
                }
                count = 0;
            }
        }
        cout << ans << endl;
    }
}